package wh.相同的树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/4/1 19:49
 * @description:给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode p = new TreeNode(1,new TreeNode(2),new TreeNode(3));
        TreeNode q = new TreeNode(1,new TreeNode(2),new TreeNode(3));
        boolean sameTree = isSameTree3(p, q);
        System.out.println(sameTree);

    }
    //解法1深度优先遍历
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            //只有&&两边均为true，才能返回true
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    //解法2广度优先遍历
    public static boolean isSameTree2(TreeNode p, TreeNode q) {
        Queue<TreeNode> tmpQueue = new LinkedList<TreeNode>();
        //入队
        tmpQueue.offer(p);
        tmpQueue.offer(q);
        while(!tmpQueue.isEmpty()){
            //出队
            p = tmpQueue.poll();
            q = tmpQueue.poll();
            if(p == null && q == null){
                continue;
            }
            if((p == null || q == null) || p.val != q.val){
                return false;
            }
            tmpQueue.offer(p.left);
            tmpQueue.offer(q.left);

            tmpQueue.offer(p.right);
            tmpQueue.offer(q.right);
        }
        return true;
    }

    //解法3 该思想基本和解法1相同
    public static boolean isSameTree3(TreeNode p,TreeNode q){
        List<String> list = new ArrayList<>();
        List<String> stringList = same(p, q, list);
        boolean aFalse = stringList.contains("false");
        return !aFalse;

    }
    public static List<String> same(TreeNode p,TreeNode q,List<String> list){
        if(p == null && q == null){
            list.add("true");
            return list;
        }else if(p == null || q == null){
            list.add("false");
            return list;
        }else if(p.val != q.val){
            list.add("false");
            return list;
        }
        same(p.left,q.left,list);
        same(p.right,q.right,list);
        return list;

    }
}
